\documentclass[a4paper,twocolumn]{article}

\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage{subfigure}

\usepackage{caption}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[croatian]{babel}
\usepackage{lmodern}

\makeatletter
\renewcommand\thesection{\@arabic\c@section.}
\renewcommand\thesubsection{\thesection\@arabic\c@subsection.}
\renewcommand\thesubsubsection{\thesubsection\@arabic\c@subsubsection.}
\renewcommand\theequation{\@arabic\c@equation}
\renewcommand\thefigure{\@arabic\c@figure.}
\renewcommand\thetable{\@arabic\c@table.}
\makeatother

\newcommand{\engl}[1]{(engl.~\textit{#1})}
\newcommand{\engla}[2]{(engl.~\textit{#1}, #2)}

\usepackage[unicode]{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}

\usepackage{booktabs}
\usepackage{fmtcount}

\begin{document}

\title{Oblikovanje igrača Tetrisa}
\author{Mladen Marović, Marko Mihoković, Mladen Mikša i Siniša Pribil}
\maketitle

\section*{Sažetak}
\label{sec:Saz}

Tetris je popularna i stara računalna igra koja se igra na ploči određenih dimenzija i u kojoj je cilj posložiti padajuće tetromine tako da popune retke.
Pronalazak optimalnog igrača Tetrisa težak je kombinatorni problem za koji je provedno više analiza te isprobano nekoliko pristupa rješavanju.
U ovom radu ispituje se korištenje unaprijedne višeslojne neuronske mreže pri oblikovanju igrača Tetrisa.
Mreža se uči u okvirima podržanog učenja pri čemu se samo učenje mreže provodi korištenjem povratnog rasprostiranja pogreške i gradijentnog spusta.
Analizira se složenost učenja neuronske mreže da igra s određenim restrikcijama u korištenim tetrominima te uspješnost mreže u općenitom Tetrisu.
Rezultati pokazuju kako je za gotovo sve tetromine mreža bila u mogućnosti naučiti optimalnu strategiju igranja u slučaju kada se u igri pojavljuje samo jedna vrsta tetromina. Također, za
klasičnu igru Tetrisa, s pojavljivanjem svih tetromina, rezultati učenja mreže su zadovoljavajući.

\section{Uvod}
\label{sec:Uvo}
Tetris je popularna računalna igra koju je $1985$. godine izumio Alexey Pajitnov. Različiti oblici sastavljeni od četiri kvadratića (tzv. tetromini) padaju s vrha igraćeg polja širokog deset
i visokog dvadeset kvadratića. Igrač tijekom pada tetromine može rotirati i posmicati. Tetromino nakon pada na dno igraćeg polja ili na drugi tetromino trajno zadržava svoj položaj.
Cilj igrača je uzastopno slagati padajuće tetromine tako da popune jedan ili više redaka i na takav način postići što je moguće veći broj bodova. Tako popunjeni redak nestaje s igraće ploče,
redci iznad izbrisanog retka padaju prema dolje, a igraču se dodijeljuju bodovi ovisno o broju redaka koje je odjednom srušio. Igra završava kada struktura tetromina popuni igraće polje na
način da onemogući pojavljivanje novog tetromina.

Slika \ref{fig:tetromini} prikazuje $7$ inačica tetromina koji se pojavljuju unutar igre. Redom su prikazani, $I$, $J$, $L$ i $O$ tetromini u prvom te $S$, $T$ i $Z$ tetromini u drugom
retku.

U sklopu ovog rada ispitivana je uspješnost igranja Tetrisa za neuronsku mrežu učenu kombinacijom nadziranog i podržanog učenja. Iako se igra čovjeku može činiti jednostavnom, zbog velikog
broja mogućih kombinacija treuntnog stanja na igraćem polju i tetromina kojeg je potrebno smjestiti, pronalazak optimalne strategije igranja Tetrisa težak je kombinatorni problem. Upravo
nas je ta činjenica, uz iznimnu popularnost ove igre, potaknula da za rad na projektu odaberemo ovu temu.

Za potrebe rada korištena su djelomično izmijenjena pravila igre Tetris. Igraće polje koje se koristi širine je šest i visine dvanaest kvadratića. Bodovanje se vrši na sljedeći način, ovisno
o broju srušenih redaka: \emph{jedan redak} -- $100$ bodova, \emph{dva retka} -- $300$ bodova, \emph{tri retka} -- $500$ bodova i \emph{četiri retka} -- $800$ bodova. Također, kraj (gubitak)
igre boduje se s $-800$ bodova.

Rad je organiziran kako slijedi. Sljedeći odjeljak predstavlja kratak pregled srodnih radova i istraživanja na temu. Zatim slijedi kratko predstavljanje neuronske mreže i opis značajki koje
određuju trenutno stanje igraće ploče. Nakon toga opisan je postupak učenja neuronske mreže te su prikazani i komentirani rezultati. Posljednji odlomak iznosi zaključak rada.

\begin{figure}
  \centering
  \includegraphics[width=0.9\linewidth]{img/Tetromini}
  \caption{Izgled tetromina.}
  \label{fig:tetromini}
\end{figure}

\section{Srodni radovi}
\label{sec:SroRad}
Postoji mnogo radova koji se bave problematikom igranja Tetrisa. Tako su, na primjer, Demaine et al.\ \cite{demaine2008tetris} dokazali kako je maksimizacija broja srušenih redaka u Tetrisu NP-potpun
problem, čak i u slučaju da je redoslijed pojavljivanja tetromina unaprijed poznat.

Brzustowski \cite{brzustowski1992can} proučava teorijsku podlogu igre, s ciljem pronalaska odgovora na pitanje može li se pronaći univerzalna pobjednička strategija, takva da igrač (pod uvjetom da ima
dovoljno vremena za donošenje odluke) može beskonačno dugo igrati. Autor problemu pristupa na način da ispituje uspješnost različitih strategija. Naposlijetku zaključuje kako postoje nizovi
tetromina koji sigurno dovode do gubitka igre, pa tako i da univerzalna dobitna strategija ne postoji.

Potaknuti zaključcima navedenim u \cite{demaine2008tetris} i drugim srodnim radovima, Bohm et al.\ \cite{bohm2005evolutionary} i Chen et al.\ \cite{chen2009apply} problemu maksimizacije broja srušenih redaka
pristupaju metaheuristikama: evolucijskim algoritmima i optimizacijom kolonijom mrava. Također, Bohm et al.\ \cite{bohm2005evolutionary} u svom radu određuju veći broj značajki na temelju kojih vrednuju
dobivena rješenja, a kao funkciju dobrote koriste linearne ili eksponencijalne težinske sume navedenih značajki. Postignuti rezultati iznimno su zadovoljavajući, pri čemu se broj srušenih
redaka prije kraja igre broji u stotinama tisuća. Chen et al.\ \cite{chen2009apply} svojom metodom postižu relativno lošije rezultate od Bohm et al.\ \cite{bohm2005evolutionary}, ali i dalje veoma zadovoljavajuće. 

\section{Neuronska mreža i značajke}
\label{sec:NeuMreZna}

Umjetna neuronska mreža biološki je inspiriran matematički model 
sastavljen od međusobno povezanih manjih procesnih elemenata -- neurona.
Postoji mnoštvo načina povezivanja neurona u mrežu, a jedan od često korištenih 
načina je unaprijedna slojevitost bez povratnih veza. U ovom radu 
korišteno je upravo takvo povezivanje slojeva.

Slojevita neuronska neuronska mreža sastoji se od tri vrste slojeva neurona:
\begin{itemize}
	\item ulazni sloj -- nakupina neurona koje ne obrađuju informacije 
			već služe za preslikavanje ulaznih podataka ostatku mreže.
	\item skriveni sloj -- nakupina neurona čija je svrha obraditi informacije
			dobivene iz ulaznog sloja ili prethodnog skrivenog sloja. 
			Obrađene informacije prosljeđuje u sljedeći sloj, 
			koji može biti skriveni ili izlazni sloj.
	\item izlazni sloj -- služi za prikaz rezultata mreže.
\end{itemize}
Količina neurona u ulaznom i izlaznom sloju ograničena je količinom ulaznih i izlaznih varijabli, dok je broj skrivenih slojeva i
količina neurona u pojedinom sloju proizvoljna. Mijenjanjem veličine i broja skrivenih slojeva utječe se na složenost modela.
Osim parametara veličine i broja skrivenih slojeva, na karakteristike mreže utječe i odabrana aktivacijska funkcija neurona. Najčešće
korištena funkcija je sigmoidalna, ali je za potrebe ovoga rada odabran tangens hiperbolni. 

Mreža na ulazima očekuje stanje na ploči, a na izlazu vraća ocjenu akcije (što je detaljnije opisano u sljedećem odsječku). 
Stanje na ploči prvotno je mreži bilo predočeno binarnim vektorom popunjenosti svih redaka, ali takav pristup nije značajnije doprinio pozitivnim
rezultatima. Navedeni problem riješen je upotrebom više različitih značajki za opis stanja ploče.
Ploča je opisana sljedećim značajkama \cite{bohm2005evolutionary,chen2009apply}:
\begin{enumerate}
	\item Visina naslaganih tetromina -- redak s najviše zauzetog mjesta na ploči.
	\item Rupe -- broj svih praznina koje iznad sebe imaju barem jedno zauzeto mjesto.
	\item Povezane rupe -- broj vertikalno povezanih rupa koje iznad sebe imaju barem jedno popunjeno mjesto.
	\item Srušeni redovi -- broj redaka uklonjenih zadnjim potezom, kojime je dobiveno trenutno stanje ploče.
	\item Razlika visina -- razlika visine između najvišeg zauzetog stupca i stupca s najvećom prazninom u koji se može smjestiti  
			tetromino.
	\item Najveća praznina stupca -- najveća praznina stupca u koju se može smjestiti tetromino.
	\item Zbroj svih praznina -- zbroj svih praznina stupaca u koje se može smjestiti tetromino.
	\item Posljednja visina tetromina -- visina na koju je smješten posljednji tetromino.
	\item Popunjenost -- broj zauzetih mjesta u svim stupcima.
	\item Težinska popunjenost -- slično kao prethodna točka, uz izmjenu da se zauzeta mjesta u $n$-tom retku broje $n$ puta više od onih u prvom retku.
	\item Isprekidanost retka -- zbroj svih prijelaza između popunjenog mjesta i praznine u retku. U razmatranje prijelaza ulaze i 
				praznine lijevo i desno izvan ploče.
	\item Isprekidanost stupca -- zbroj svih prijelaza između popunjenog mjesta i praznine u stupcu. U razmatranje prijelaza ulaze 
				i praznine iznad i ispod ploče.
	\item Najviša praznina -- visina najviše praznine na ploči.
	\item Popunjenost iznad najviše praznine -- količina popunjenih mjesta iznad najveće praznine.
	\item Potencijalne linije -- broj linija iznad najveće praznine, koje pritom zauzimaju više od 8 mjesta.
	\item Zaglađenost -- zbroj svih apsolutnih razlika susjednih visina stupaca, uključujući i razliku prvog i zadnjeg stupca.
\end{enumerate}


\section{Učenje neuronske mreže}
\label{sec:UceNeuMre}

Cilj je učenja neuronske mreže naučiti mrežu da igra tako da ostvari što je više moguće bodova u Tetrisu.
Kako se bodovi ostvaruju rušenjem redaka, mreža treba naučiti izabrati rotaciju i poziciju tetromina tako da sruši što je više moguće redaka.
U slučajevima kada se rušenje redaka može ostvariti, relativno je lako odabrati poziciju na koju se tetromino postavlja.
Za razliku od takvih poteza, većina ih ne može rezultirati rušenjem redaka, pa se javlja problem kako ocijeniti njihovu kvalitetu.
U svrhu rješenja tog problema koristi se podržano učenje neuronske mreže.

Podržano je učenje metoda u kojoj agent, u ovom slučaju neuronska mreža, uči u interakciji s okolinom (pločom za Tetris).
Korištenjem podržanog učenja agent uči niz akcija koje treba napraviti da ostvari najveću nagradu (sruši najviše redaka u igri).
Pritom je potrebno kombinirati utjecaj nagrade koji se dobiva trenutnom akcijom agenta i kvalitete stanja u koje agent dolazi provođenjem zadane akcije.
U podržanom učenju agent ne dobiva primjere koje treba naučiti, već sam mora istražiti okolinu i pronaći odgovarajuće akcije.

U radu se za podržano učenje koristi metoda Q-učenja \cite{sutton1998reinforcement}.
Ta metoda uči agenta funkciju kvalitete $Q$ akcije $a_t$ za zadano stanje $s_t$.
Pritom se funkcija $Q$ uči iz iskustva uz mijenjanje procjene kvalitete akcije $Q$ pri svakoj akciji, umjesto da se čeka konačan rezultat igre.
Zbog toga se pri samom računanju kvalitete trenutne akcije koristi do tada izračunata procjena kvalitete kako bi se odredila kvaliteta budućeg stanja.
Odnosno, koristimo vrijednost procjene funkcije $Q$ za sljedeći trenutak kako bi ispravili trenutnu procjenu mreže.
Promjena funkcije kvalitete za trenutak $t$ u kojem se provodi akcija $a_t$ za stanje $s_t$ definira se izrazom:
\begin{multline*}
  Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \\
  \eta [r_{t + 1} + \gamma \max_a Q(s_{t + 1}, a) - Q(s_t, a_t)].
\end{multline*}
S $r_{t + 1}$ predstavljena je trenutna nagrada koja se dobiva provođenjem akcije $a_t$ za stanje $s_t$.
Izraz $\gamma \max_a Q(s_{t + 1}, a)$ izražava kvalitetu idućeg stanja u koje se dolazi provođenjem zadane akcije $a_t$.
Parametar $\gamma$ određuje koliku važnost pridajemo kvaliteti budućeg stanja u odnosu na vrijednost trenutne nagrade $r_{t + 1}$.
Stopa učenja dana je parametrom $\eta$ i predstavlja veličinu promjene vrijednosti procjene funkcije $Q$ u danom koraku.
Nakon što nauči funkciju $Q$, agent na okolinu reagira tako da za stanje $s_t$ bira onu akciju $a_t$ koja daje najveću vrijednost funkcije $Q$.

Prilikom primjene Q-učenja na neuronsku mrežu i igru Tetris provedeno je nekoliko modifikacija izvornog pravila.
Prvo je sam Tetris pojednostavljen tako da se ne uzima postojanje prozora s prikazom sljedećeg tetromina.
Zbog toga je stanje u trenutku $t$ definirano uređenim parom $(b_t, p_t)$, gdje $b_t$ označava stanje ploče u danom trenutku, dok $p_t$ označava tetromino kojeg se treba postaviti na ploču.
Mreža treba naučiti funkciju $Q(b, p, a)$ gdje akcija $a$ određuje poziciju i rotaciju tetromina $p$.
Neuronska mreža uči se uobičajenom metodom povratnog rasprostiranja pogreške uz funkciju greške:
\[
E_t = \frac{1}{2} (o_t - y_t)^2,
\]
gdje je $y_t$ izlaz mreže u trenutku $t$, dok je $o_t$ željeni izlaz koji se definira korištenjem ideja Q-učenja.
Uz zadani $o_t$ promjena težine $w_{ji}$ neuronske mreže provodi se gradijentnim spustom definiranim izrazom:
\[
w_{ji} \leftarrow w_{ji} - \eta \frac{\partial E_t}{\partial w_{ji}}.
\]

Za zadavanje željenog izlaza neuronske mreže $o_t$ mora se malo modificirati izvorna ideja Q-učenja.
U prethodno predstavljenom Q-učenju željeni izlaz $\tilde{o}_t$ bio bi definiran formulom:
\[
\tilde{o}_t = r_{t + 1} + \gamma \max_a Q(b_{t + 1}, p_{t + 1}, a),
\]
gdje je s trenutnom nagradom $r_{t + 1}$ obuhvaćena skalirana vrijednost bodova koje je potez donio na interval $[0, 1]$.
U slučaju da potez vodi na gubitak igre, trenutna nagrada $r_{t + 1}$ jednaka je $-1$.
Prva je modifikacija izraza dodavanje faktora $(1 - \gamma)$ uz član $r_{t + 1}$, kako bi se željeni izlaz mreže ograničio na raspon $[-1, 1]$ u kojem mreža vraća vrijednosti.
Problem kod računanja vrijednosti $max_a Q(b_{t + 1}, p_{t + 1}, a)$ je da nije poznat sljedeći tetromino $p_{t + 1}$.
Kako nije realno za pretpostaviti da će doći tetromino koji rezultira optimalnim potezom, računa se aritmetička sredina vrijednosti optimalnih poteza za sve moguće tetromine.
Neka je s $\mathcal{P}$ zadan skup svih tetromina, željena vrijednost akcije $o_t$ u trenutku $t$ se račun po formuli:
\[
o_t = (1 - \gamma) r_{t + 1} + \gamma \frac{1}{|\mathcal{P}|} \sum\limits_{p \in \mathcal{P}} \max_a Q(b_{t + 1}, p, a).
\]

Učenje se provodi tako da mreža igra Tetris i prilikom igranja mijenja svoje težine po prethodno opisanom pravilu.
Mreža pri igranju iskorištava trenutnu procjenu funkcije $Q$ kako bi odlučila koju će akciju provesti.
Kada bi se kao akcija birala uvijek ona koja rezultira najvećom vrijednosti funkcije $Q$ mreža bi previše težila učenju jedne strategije.
Kako takva strategija ne mora biti optimalna, potrebno je omogućiti mreži da pri učenju istraži i druge opcije.
Istraživanje bi se moglo posebno naglasiti kada bi se sljedeća akcija birala slučajnim odabirom, ignorirajući vrijednosti funkcije $Q$.
U takvom načinu učenja mreža bi teško učila neku određenu strategiju, jer niti jedna strategija ne bi bila posebno podržana poticanjem ponavljanja koraka.
Taj problem naziva se problemom iskorištavanja i istraživanja u kojem je cilj pronaći omjer između ta dva pristupa kojim će se naučiti najbolja strategija.

U ovom radu koristi se algoritam softmax za rješavanje problema iskorištavanja i istraživanja \cite{sutton1998reinforcement}.
Neka je s $\mathcal{A}$ označen skup mogućih akcija (pozicija i rotacija tetromina) koje je moguće izvršiti za zadano stanje ploče $b$ i figuru $p$.
Algoritam softmax bira akciju $a'$ s vjerojatnošću $P$ zadanu izrazom:
\[
P(a') = \frac{e^{Q(b, p, a')}}{\sum\limits_{a \in \mathcal{A}} e^{Q(b, p, a)}},
\]
gdje je $\tau$ parametar kojim određujemo utjecaj istraživanja u odnosu na iskorištavanje naučene strategije.
Kada $\tau$ teži nuli odabire se akcija za koju mreža daje veću vrijednost funkcije $Q$, dok u slučaju kada $\tau$ teži u beskonačnost sve akcije imaju jednaku vjerojatnost izbora.

Prilikom učenja mreže ispostavilo se da uz korištenje samo podržanog učenja mreža sporo konvergira prema kvalitetnoj strategiji igranja Tetrisa.
Zbog toga je implementirano i nadzirano učenje kojim se neuronska mreža prvo pokušava naučiti neke prihvatljive strategije sadržane u primjerima za učenje.
Nakon početnog nadziranog učenja, provodi se podržano učenje kako bi mreža mogla doći u kontakt s drugim situacijama i naučiti bolju strategiju od one sadržane u primjerima.
U samom ostvarenju nadziranog učenja jedina promjena je da mreža ima unaprijed zadane ploče i tetromine, kao i akciju koju provodi, zadane skupom za učenje.
Time je osigurano da mreža prvo uči akcije igrača iz skupa za učenje, čime utvrdi neku početnu zadovoljavajuću strategiju koju poboljšava naknadnim podržanim učenjem.

\section{Eksperimenti}
\label{sec:Eks}

\begin{table*}
  \caption{Rezultati eksperimenata s restrikcijama tetromina.}
  \centering
  {\scriptsize
    \begin{tabular}{@{\extracolsep{0pt}}ccccccrr}
      \toprule
      & & \multicolumn{4}{c}{Parametri učenja} & & \\ 
      \cmidrule{3-6}
      Dozvoljeni tetromini & Skriveni slojevi & $\lambda$ & $\gamma$ & $\eta$ & $\tau$ & Broj poteza & Prosjek bodova \\
      \midrule
      O & 10 & 0 & 0.6 & $2 \cdot 10^{-4}$ & 0.05 & $2 \cdot 10^4$ & $\infty$ \\
      J & 20 20 & 0 & 0.6 & $2 \cdot 10^{-4}$, $3 \cdot 10^{-5}$ \footnotemark & 0.05 & $9.5 \cdot 10^5$ & $\infty$ \\
      Z & 20 20 & 0 & 0.3 & $2 \cdot 10^{-4}$ & 0.05 & $8 \cdot 10^5$ & $\infty$ \\
      S & 20 20 & 0 & 0.3 & $2 \cdot 10^{-4}$ & 0.05 & $4 \cdot 10^5$ & $\infty$ \\
      I & 10 & 0 & 0.3 & $2 \cdot 10^{-4}$ & 0.05 & $3 \cdot 10^4$ & $\infty$ \\
      T & 10 10 & 0 & 0.3 & $2 \cdot 10^{-4}$ & 0.05 & $3 \cdot 10^5$ & $\infty$ \\
      O + I & 25 25 & 0 & 0.3 & $2 \cdot 10^{-4}$ & 0.05 & $3.6 \cdot 10^5$ & 5702.7 \\
      J + L & 20 20 & 0 & 0.3, 0.5, 0.6 \footnotemark & $2 \cdot 10^{-4}$ & 0.05 & $1.2 \cdot 10^6$ & 7891.8 \\
      \bottomrule
    \end{tabular}
  }
  \label{tbl:rezEksOgr}
\end{table*}

\begin{table*}
  \caption{Proces učenja najuspješnije mreže.}
  \centering
  {\small
    \begin{tabular}{c c c c c c r}
      \toprule
      & & \multicolumn{4}{c}{Parametri učenja} & \\ 
      \cmidrule{3-6}
      Broj koraka & Vrsta učenja & $\lambda$ & $\gamma$ & $\eta$ & $\tau$ & Broj poteza \\
      \midrule
      1 & nadzirano & 0 & 0.1 & $2 \cdot 10^{-4}$ & --- & $6 \cdot 10^4$ \\
      2 & nadzirano & 0 & 0.2 & $1 \cdot 10^{-5}$ & --- & $2.5 \cdot 10^5$ \\
      3 & nenadzirano & 0 & 0.3 & $2 \cdot 10^{-4}$ & 0.05 & $1.3 \cdot 10^6$ \\
      4 & nenadzirano & 0 & 0.5 & $2 \cdot 10^{-4}$ & 0.05 & $5 \cdot 10^4$ \\
      \bottomrule
    \end{tabular}
  }
  \label{tbl:paramUčNaj}
\end{table*}

Za potrebe rada bilo je potrebno izgraditi odgovarajući skup za učenje i provesti
eksperimente koji prikazuju ponašanje neuronske mreže. Pritom su se mijenjale
ulazne značajke, restrikcije korištenih tetromina, parametri učenja, duljina
učenja i vrste učenja.

Za potrebe nadziranog učenja igranjem Tetrisa i pamćenjem poteza skupljeno je
$2838$ primjera. Ti primjeri sadržavali su podatke o stanju ploče, trenutnom
tetrominu, opisu odigranog poteza (rotacija lika i stupac na kojem je postavljen)
i broju pobrisanih redaka u tom potezu. Prilikom igranja Tetrisa primijećeno je
da je kod većine poteza barem neki dio ploče popunjen, dok je primjera s početka
igre i sa skoro praznom pločom vrlo malo. S druge strane, potezi na početku igre
mogu imati veliki utjecaj na ostatak partije. Stoga je $2038$ poteza skupljeno iz
uobičajenog igranja Tetrisa, dok je pri izradi posljednjih $800$ primjera nakon
svakih $10$ poteza započeta nova partija.

Kao što je opisano u \ref{sec:NeuMreZna}, prvotno je mreža kao ulaz primala i
čitavo stanje ploče. Međutim, eksperimenti provedeni nad mrežom s ovakvim ulazima
dali su vrlo loše rezultate. Čak i nakon duljeg učenja koje je trajalo $2.5 \cdot
10^6$ poteza mreža nije davala zadovoljavajuće rezultate igrajući Tetris.
Štoviše, u većini igara odigranih tijekom učenja mreža nije uspjela pobrisati
niti jedan redak. Stoga su odabrane nove ulazne značajke koje su se koristile u
daljnjim eksperimentima.

\addtocounter{footnote}{-2}
\stepcounter{footnote}\footnotetext[\value{footnote}]{U prvih $9 \cdot 10^5$
poteza korištena je vrijednost $\eta= 2 \cdot 10^{-4}$, a u zadnjih $5 \cdot 10^4$ $\eta= 3 \cdot
10^{-5}$.}
\stepcounter{footnote}\footnotetext[\value{footnote}]{U prvih $6 \cdot 10^5$
poteza korištena je vrijednost $\gamma = 0.3$, u drugih $3 \cdot 10^5$ $\gamma = 0.5$, a u zadnjih
$3 \cdot 10^5$ $\gamma = 0.6$.}

Dio eksperimenata obuhvaćao je i smanjivanje broja dozvoljenih vrsta tetromina u
partijama. Cilj ovih eksperimenata bio je provjeriti tvrdnju da je s nekim
tetrominima teže igrati. Rezultati ovih eksperimenata prikazani su u tablici
\ref{tbl:rezEksOgr}. Za svaki eksperiment prikazani su: restrikcija korištenih
tetromina, struktura skrivenih slojeva mreže (brojevi neurona u pojedinim
skrivenim slojevima), vrijednosti parametara učenja, duljina trajanja učenja
izražena brojem poteza i prosjek bodova osvojenih u $1000$ partija. Ako je
dozvoljena samo jedna vrsta tetromina, tada oznaka $\infty$ znači da je mreža
naučila strategiju za igranje partije bez kraja, tj. optimalnu strategiju za taj
tetromino. Rezultati pokazuju da su u eksperimentima na pojedinačnim dozvoljenim
tetrominima uspješno naučene optimalne strategije za sve tetromine osim za
tetromino L. U slučaju parova tetromina, mreža za odabrane parove nije naučila
optimalnu strategiju, ali je davala solidne rezultate pri igranju.

Cilj posljednjeg eksperimenta bio je pronaći mrežu koja će davati zadovoljavajuće
rezultate pri igranju Tetrisa sa svim tetrominima. Različitim
kombinacijama vrsta učenja i parametara naučeno je nekoliko mreža te su koraci
učenja najuspješnije mreže prikazani u tablici \ref{tbl:paramUčNaj}.
Slike \ref{fig:proProg1}--\ref{fig:proPog3} prikazuju promjene pogrešaka
tijekom različitih koraka učenja mreže te promjene osvojenih bodova i duljina
partija. Nakon prikazanog procesa učenja ploča je u $1000$ partija postigla
prosječan rezultat od $3655.8$.

\section{Zaključak}
\label{sec:Zak}

U ovom radu ispitana je uspješnost unaprijedne višeslojne neuronske mreže u učenju igranja Tetrisa.
Za učenje mreže korišteno je povratno rasprostiranje pogreške u okvirima podržanog učenja.
Ispitana je složenost učenja mreže za nekoliko različitih restrikcija korištenih tetromina.
Rezultati prikazuju da se za tetromine $O$ i $I$ učenjem jednostavne mreže mogu
brzo naučiti optimalne strategije, dok je za tetromine $J$ i $Z$ potrebna
složenija mreža i dulji proces učenja. Za tetromino $L$ nije pronađena mreža
koja uči optimalnu strategiju. Ukoliko se koriste svi tetromini, mreža može
naučiti igrati Tetris tako da daje zadovoljavajuće rezultate.

Kako je iz rezultata vidljivo da mreža teže uči s nekim tetrominima u odnosu na druge, potrebno bi bilo analizirati značajke i njihove mogućnosti obuhvaćanja pojedinih tetromina.
Također, u tu svrhu trebalo bi razmotriti i mogućnost dodavanja novih značajki koje bi davale više informacija o stanju ploče i provedenoj akciji.
Dodatno, detaljnije ispitivanje utjecaja parametara učenja i strukture mreže moglo bi doprinijeti poboljšanju rezultata.
U formuli kojom je definirana željena vrijednost funkcije $Q$, vrijednost trenutne akcije ne kažnjava mrežu ako ne sruši retke premda je u mogućnosti to učiniti.
Modificiranje pravila tako da obuhvati tu kaznu moglo bi dovesti do bržeg učenja mreže i bolje konačne strategije.
U slučaju pronalaska mreže koja bi posebno dobro igrala Tetris, moglo bi se ispitati i dodavanje suparničkog igrača koji bi birao koji tetromino dolazi sljedeći na ploču.
Dodavanjem takvog suparničkog igrača moglo bi se provesti ispitivanje međusobnog razvoja njihovih strategija i sposobnosti da nadmaše jedan drugoga.

\bibliographystyle{plain}
\bibliography{izvjestaj}

\section*{Dodatak}
\label{Dod}

Popis korištenih matlab funkcija i skripti:
\begin{itemize}
\item \emph{assignTableActionPairs} -- funkcija za igranje Tetrisa, vraća sve vrijednosti tablica, tetromina i akcija koje je korisnik učinio tijekom igranja,
\item \emph{calculateGradients} -- računa gradijente težina za zadani ulaz mreže i željeni izlaz, koji se koriste prilikom učenja mreže,
\item \emph{calculateNewWeights} -- računa nove težine mreže uz zadane gradijente i stopu učenja $\eta$,
\item \emph{costFunction} -- računa vrijednost funkcije greške za zadanu mrežu,
\item \emph{dispTable} -- prikazuje u komandnoj liniji izgled predane tablice Tetrisa,
\item \emph{estimateNextMoveQuality} -- procjenjuje kvalitetu sljedećeg stanja definiranu s $\frac{1}{|\mathcal{P}|} \sum\limits_{p \in \mathcal{P}} \max_a Q(b_{t + 1}, p, a)$,
\item \emph{formInputs} -- formira ulaze mreže za zadanu tablicu i tetromino,
\item \emph{generateTetromino} -- vraća izgled zadanog tetromina uz danu rotaciju,
\item \emph{getLegalMoves} -- dohvaća sve moguće dozvoljene poteze za zadani tetromino,
\item \emph{initWeights} -- inicijalizira težine mreže na slučajne vrijednosti,
\item \emph{performLearn} -- skripta s kojom se provodi potpuno učenje mreže uz zadane parametre,
\item \emph{performLearnLimited} -- skripta s kojom se provodi samo podržano učenje mreže uz zadavanje koji se tipovi tetromina koriste u igri,
\item \emph{performMove} -- provodi postavljanje tetromina na ploču i računa dodatne informacije potrebne za stvaranje ulaza mreže,
\item \emph{performQLearn} -- funkcija iz koje se provodi podržano učenje koja crta graf kretanja pogreške te grafove ukupnih bodova i trajanja partija Tetrisa,
\item \emph{performSupervisedLearn} -- funkcija koja provodi nadzirano učenje i crta graf kretanja pogreške tijekom iteracija učenja,
\newpage{}
\item \emph{playTetris} -- skripta iz koje se pokreće igranje Tetrisa za generiranje primjera za učenje,
\item \emph{predictQuality} -- vraća izlaze neuronske mreže za zadane ulaze,
\item \emph{qLearn} -- provodi podržano učenje neuronske mreže,
\item \emph{seeNeuralNetworkPlay} -- prikazuje igranje jedne partije neuronske mreže u komandnoj liniji,
\item \emph{seeNeuralNetworkPlayGUI} -- prikazuje igranje jedne partije neuronske mreže u grafičkom sučelju i
\item \emph{supervisedLearn} -- provodi nadzirano učenje mreže.
\end{itemize}

\begin{figure*}[p]
  \centering
  \subfigure[]{
    \includegraphics[width=0.35\linewidth]{img/supervised_1.eps}  
    \label{fig:proProg1_1}
  }
  \subfigure[]{
    \includegraphics[width=0.35\linewidth]{img/supervised_2.eps}  
    \label{fig:proProg1_2}
  }
  \caption{%
    Prikaz promjene pogreške tijekom nadziranog učenja:
    \subref{fig:proProg1_1} promjena tijekom prvog koraka učenja;
    \subref{fig:proProg1_2} promjena tijekom drugog koraka učenja.
  }
  \label{fig:proProg1}
\end{figure*}

\begin{figure*}[p]
  \centering 
  \subfigure[]{
    \includegraphics[width=0.35\linewidth]{img/qlearn_1.eps}
    \label{fig:proPog2_1}
  }
  \subfigure[]{
    \includegraphics[width=0.35\linewidth]{img/qlearnMoves_1.eps}
    \label{fig:proPog2_2}
  }
  \subfigure[]{
    \includegraphics[width=0.35\linewidth]{img/qlearnScores_1.eps}
    \label{fig:proPog2_3}
  }
  \caption{%
    Prikaz trećeg koraka učenja:
    \subref{fig:proPog2_1} promjena pogreške;
    \subref{fig:proPog2_2} promjena duljine partije;
    \subref{fig:proPog2_3} promjena osvojenih bodova.
  }
  \label{fig:proPog2}
\end{figure*}

\begin{figure*}[p]
  \centering 
  \subfigure[]{
    \includegraphics[width=0.4\linewidth]{img/qlearn_2.eps}
    \label{fig:proPog3_1}
  }
  \subfigure[]{
    \includegraphics[width=0.4\linewidth]{img/qlearnMoves_2.eps}
    \label{fig:proPog3_2}
  }
  \subfigure[]{
    \includegraphics[width=0.4\linewidth]{img/qlearnScores_2.eps}
    \label{fig:proPog3_3}
  }
  \caption{%
    Prikaz četvrtog koraka učenja:
    \subref{fig:proPog3_1} promjena pogreške;
    \subref{fig:proPog3_2} promjena duljine partije;
    \subref{fig:proPog3_3} promjena osvojenih bodova.
  }
  \label{fig:proPog3}
\end{figure*}

\end{document} 
